package com.xiaotao.learn.algorithm.sort;

import java.util.Arrays;

class QuickSort {
    private static void swap(int[] input, int i, int j) {
        int t = input[i];
        input[i] = input[j];
        input[j] = t;
    }
    private static int baseSort(int[] input, int l, int r) {
        int base = input[r];
        while (l < r) {
            while (l < r && input[l] < base) {
                l++;
            }
            if(l < r) {
                input[r--] = input[l];
                //swap(input, l, r--);
            }
            while (l < r && input[r] > base) {
                r--;
            }
            if (l < r) {
                input[l++] = input[r];
                //swap(input, l++, r);
            }
        }
        input[l] = base;
        return l;
    }
    private static void sort(int[] input, int l, int r) {
        if(l >= r) return;
        int base = baseSort(input, l, r);
        sort(input, l, base - 1);
        sort(input, base + 1, r);
    }

    /**
     * 对数组进行快排
     * @param input 需要排序的数组
     */
    public static void sort(int[] input) {
        sort(input, 0, input.length - 1);
    }
}

public class QuickSortTest {
    public static void main(String[] args) {
        int[] input = new int[]{114514,1,9,2,3,6,5,12,5,1,15,24,62,0,9,-3,-114514};
//        int[] input = new int[]{5,2,4,1};
        QuickSort.sort(input);
        System.out.println(Arrays.toString(input));
    }
}
